package 二叉树;
import java.util.*;

public class flatten {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){ this.val = val;}
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // 将二叉树展开为链表
    public static void flattenm(TreeNode root) {
        // 使用一个列表存储二叉树的节点 
        List<TreeNode> list = new ArrayList<>();
        // 使用深度优先搜索遍历二叉树
        dfs(root, list);
        // 遍历列表，将每个节点的左子树设置为null，右子树设置为下一个节点
        int size = list.size();
        // 从第二个节点开始遍历
        for(int i = 1; i < size; i++) {
            // 获取当前节点和前一个节点
            TreeNode prev = list.get(i-1), curr = list.get(i);
            // 将当前节点的左子树设置为null
            prev.left = null;
            // 将当前节点的右子树设置为下一个节点
            prev.right = curr;
        }
    }
    // 使用深度优先搜索遍历二叉树
    public static void dfs(TreeNode root, List<TreeNode> list) {
        if(root == null) return;
        // 将当前节点加入列表
        list.add(root);
        // 递归遍历左子树
        dfs(root.left, list);
        // 递归遍历右子树
        dfs(root.right, list);
    }
    // 构建二叉树
    public static TreeNode buildTree(String[] nodes) {
        // 如果节点为空，则返回null
        if(nodes == null || nodes.length == 0 || nodes[0].equals("null"))
            return null;
        // 创建根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        // 使用一个队列存储节点
        Deque<TreeNode> deque = new LinkedList<>();
        // 将根节点加入队列
        deque.offer(root);
        // 从第二个节点开始遍历
        int index = 1;
        // 如果队列不为空且索引小于节点数，则继续遍历
        while(!deque.isEmpty() && index < nodes.length) {
            // 获取队列中的节点
            TreeNode node = deque.poll();
            // 如果当前节点不为空，则将左子节点加入队列
            if(index < nodes.length &&!nodes[index].equals("null")) {
                // 创建左子节点
                node.left = new TreeNode(Integer.parseInt(nodes[index]));
                // 将左子节点加入队列
                deque.offer(node.left);
            }
            // 索引加1
            index++;
            // 如果当前节点不为空，则将右子节点加入队列
            if(index < nodes.length &&!nodes[index].equals("null")) {
                // 创建右子节点
                node.right = new TreeNode(Integer.parseInt(nodes[index]));
                // 将右子节点加入队列
                deque.offer(node.right);
            }
            // 索引加1
            index++;
        }
        // 返回根节点
        return root;
    }
    // 主方法
    public static void main(String[] args) {
        // 使用Scanner读取输入
        Scanner sc = new Scanner(System.in);
        // 读取输入的节点，以逗号分隔
        String[] nodes = sc.nextLine().split(",");
        // 构建二叉树
        TreeNode root = buildTree(nodes);
        // 将二叉树展开为链表
        flattenm(root);
        // 遍历链表
        while(root != null) {
            // 输出当前节点的值
            System.out.print(root.val + " ");
            // 移动到下一个节点
            root = root.right;
        }
        // 关闭Scanner
        sc.close();
    }
    
}
